#include "ThreadedBinaryTree.hpp"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream>

ThreadedBinaryTreeNode* buildNode(const char* data);

ThreadedBinaryTree::ThreadedBinaryTree(int mode, const char* rootData) {
    this->mode = mode;
    this->root = buildNode(rootData);
}

ThreadedBinaryTreeNode* ThreadedBinaryTree::inorderSuccessor(ThreadedBinaryTreeNode* p) {
    ThreadedBinaryTreeNode* position;
    if (p->lTag == 0 && p->left == nullptr)
        return p;
    else {
        position = p->right;
        while (position->lTag == 0)
            position = position->left;
        return position;
    }
}

ThreadedBinaryTreeNode* ThreadedBinaryTree::insertNode(const char* data) {
    ThreadedBinaryTreeNode* node = buildNode(data);
    ThreadedBinaryTreeNode* p;
    ThreadedBinaryTreeNode* pp;
    p = this->root;
    pp = this->root;
    int cmpr;
    int direction = 0;
    for (;;) {
        cmpr = strcmp(p->data, data);
        if (cmpr == 0) {
            break;
        }
        if (cmpr < 0) { //新增右节点
            direction = direction == 0 || direction == 1 ? 1 : -1;
            if (p->right == nullptr || p->rTag == 1) {
                p->rTag = 0;
                p->right = node;
                if (mode == 1) {
                    node->lTag = 1;
                    node->left = p;
                    node->rTag = direction == 1 ? 0 : 1;
                    node->right = direction == 1 ? nullptr : pp;
                }
                break;
            }
            else {
                pp = p;
                p = p->right;
            }
        }
        else { //新增左节点
             direction = direction == 0 || direction == 2 ? 2 : -1;
            if (p->left == nullptr || p->lTag == 1) {
                p->left = node;
                p->lTag = 0;
                if (mode == 1) {
                    node->lTag = direction == 2 ? 0 : 1;
                    node->left = direction == 2 ? nullptr : p;
                    node->rTag = 1;
                    node->right = p;
                }
                break;
            }
            else {
                pp = p;
                p = p->left;
            }
        }
    }
    return node;
}

void ThreadedBinaryTree::inorderTaversal() {
    ThreadedBinaryTreeNode* p = root;;
    while (p->left != nullptr) 
        p = p->left;
    while (1) {
        printf("node(%s lr %d rr %d)",p->data,p->lTag,p->rTag);
        p = p->right;
        if (p == nullptr) {
            break;
        }
        printf("->");
    }
    std::cout << std::endl;
}

ThreadedBinaryTreeNode* ThreadedBinaryTree::getRootNode() {
    return this->root;
}

ThreadedBinaryTreeNode* buildNode(const char* data) {
    ThreadedBinaryTreeNode *newNode = (ThreadedBinaryTreeNode *)malloc(sizeof(ThreadedBinaryTreeNode));
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    newNode->rTag = 0;
    newNode->lTag = 0;
    return newNode;
}